package leetcode.N201_N300;

import java.util.Arrays;

/**
 * @author xiwai [hww282306@alibaba-inc.com]
 * @version 1.0
 * @date 2020/10/20 12:26 下午
 */
public class N215 {

    public static void main(String[] args) {
        int [] nums = {2,1,3,4};
        qSort(nums, 0, nums.length - 1);
        System.out.println(Arrays.toString(nums));
    }

    public int findKthLargest(int[] nums, int k) {
//        Arrays.sort(nums);
        qSort(nums, 0, nums.length - 1);
        return nums[nums.length - k];
    }

    private static void qSort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int val = nums[right];
        int index = left;
        // 寻找分界点
        for (int i = left; i < right; i++) {
            int currentVal = nums[i];
            if (currentVal < val) {
                nums[i] = nums[index];
                nums[index++] = currentVal;
            }
        }
        nums[right] = nums[index];
        nums[index] = val;
        qSort(nums, left, index - 1);
        qSort(nums, index + 1, right);
    }


}
